#define _CRT_SECURE_NO_WARNINGS 1

class Solution {
public:
    ListNode* GetMid(ListNode* head, ListNode* tail)
    {
        ListNode* slow, * fast;
        slow = fast = head;
        while (fast != tail && fast->next != tail)
        {
            slow = slow->next;
            fast = fast->next->next;
        }
        return slow;
    }
    TreeNode* _sort(ListNode* head, ListNode* tail)
    {
        if (head == tail)
        {
            return nullptr;
        }
        ListNode* mid = GetMid(head, tail);
        TreeNode* root = new TreeNode(mid->val);
        root->left = _sort(head, mid);
        root->right = _sort(mid->next, tail);
        return root;
    }
    TreeNode* sortedListToBST(ListNode* head)
    {
        return _sort(head, nullptr);
    }
};

class Solution {
public:
    int GetLen(ListNode* head)
    {
        int len = 0;
        for (; head != nullptr; len++, head = head->next);
        return len;
    }
    TreeNode* _sort(ListNode*& head, int left, int right)
    {
        if (left > right)
            return nullptr;
        int mid = (left + right + 1) / 2;
        TreeNode* root = new TreeNode();
        root->left = _sort(head, left, mid - 1);
        root->val = head->val;
        head = head->next;
        root->right = _sort(head, mid + 1, right);
        return root;
    }
    TreeNode* sortedListToBST(ListNode* head)
    {
        int len = GetLen(head);
        return _sort(head, 0, len - 1);
    }
};

